package com.freedy.dataStructure.stack;

/**
 * 中缀转后缀
 * 逆波兰计算器
 * @author Freedy
 * @date 2021/3/16 20:21
 */
public class PolandNotation {

    public Double calculate(String suffixExpression) {
        ArrStack<String> stack = new ArrStack<String>(30);
        StringBuilder builder = new StringBuilder();
        for (int i = suffixExpression.length() - 1; i >= 0; i--) {
            char ch = suffixExpression.charAt(i);
            if (isOps(ch)) {
                stack.push(String.valueOf(ch));
            } else if (suffixExpression.charAt(i) != ' ') {
                builder.append(suffixExpression.charAt(i));
            } else if (suffixExpression.charAt(i) == ' ' && builder.length() > 0) {
                builder.reverse();//应为是反着遍历所以要颠倒一下数字
                stack.push(builder.toString());
                builder = new StringBuilder();//清空builder
            }
        }
        //将最后的数字push到栈中
        builder.reverse();
        stack.push(builder.toString());
        ArrStack<Double> numStack = new ArrStack<Double>(30);
        try {
            while (stack.size() > 0) {
                String pop = stack.pop();
                if (!isOps(pop.charAt(0))) {
                    numStack.push(Double.parseDouble(pop));
                } else {
                    Double num1 = numStack.pop();
                    Double num2 = numStack.pop();
                    double res = cal(num1, num2, pop.charAt(0));
                    numStack.push(res);
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
            throw new RuntimeException("表达式不正确");
        }
        return numStack.pop();
    }

    /**
     * 将中缀表达式转化为后缀表达式
     *
     * @param infixExpression
     * @return
     */
    public String infixExpressionToSuffixExpression(String infixExpression) {
        StringBuilder temp = new StringBuilder();
        ArrStack<Character> s1 = new ArrStack<Character>(infixExpression.length());
        ArrStack<String> s2 = new ArrStack<String>(infixExpression.length());
        //扫描字符串
        for (int i = 0; i < infixExpression.length(); i++) {
            char charAt = infixExpression.charAt(i);
            if (isOps(charAt)) {
                if (!temp.isEmpty()) {
                    s2.push(temp.toString());
                    temp = new StringBuilder();
                }
                while (true) {
                    if (s1.isEmpty() || priority(charAt) > priority(s1.peak()) || charAt == '(') {
                        s1.push(charAt);
                        break;
                    } else if (charAt == ')') {
                        while (s1.peak() != '(') {
                            s2.push(String.valueOf(s1.pop()));
                        }
                        s1.pop();
                        break;
                    } else {
                        s2.push(String.valueOf(s1.pop()));
                    }
                }
            } else {
                temp.append(charAt);
            }
        }
        //将最后一个元素推入
        s2.push(String.valueOf(temp));
        //将s1中剩余的元素推入s2中
        while (!s1.isEmpty()) {
            s2.push(String.valueOf(s1.pop()));
        }
        //反向输出s2 构建后缀表达式
        StringBuilder suffixExpression = new StringBuilder();
        while (!s2.isEmpty()) {
            suffixExpression.insert(0,s2.pop()+" ");
        }
        return suffixExpression.toString().strip();
    }

    private boolean isOps(char val) {
        return val == '+' || val == '-' || val == '*' || val == '/' || val == '(' || val == ')';
    }

    private double cal(double num1, double num2, int ops) {
        double res = 0;//存放计算结果
        switch (ops) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;
                break;
            default:
                throw new RuntimeException("计算错误");
        }
        return res;
    }

    /**
     * 判断运算符的优先级,优先级用数字来表示
     * 数字越大优先级越高
     *
     * @param ops
     * @return
     */
    private int priority(char ops) {
        //int和char可以相互转换，char的底层也是数字
        if (ops == '*' || ops == '/') {
            return 2;
        } else if (ops == '+' || ops == '-') {
            return 1;
        } else if (ops == '(' || ops == ')') {
            return 0;
        } else {
            return -1;
        }
    }
}
